package _0_6_回文子串_子序列_编辑距离

/*
原题链接:
https://leetcode.cn/problems/distinct-subsequences/

115. 不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

给你两个字符串 s 和 t, 统计并返回在 s的子序列中 t 出现的个数, 结果需要对 109+7取模

示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
*/
func numDistinct(s string, t string) int {

	m := len(s)
	n := len(t)

	dp := make([][]int, m+1) //声明dp数组
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, n+1)
	}

	//初始化
	for i := 0; i < m+1; i++ { //2.1 当目标字符串为空时, dp[i][0]都能有一种方案  2.2 dp[0][i]是来源字符串为空, 一定凑不出目标字符串,保持默认为0即可, 其它位置也保持为0即可
		dp[i][0] = 1
	}

	for i := 1; i <= m; i++ { //3. 填充dp数组  dp[i][j]: 以i-1为结尾的字符串1, 和以j-1为结尾的字符串2, 通过删除能够拼凑出字符串2的方案数  所以遍历从1开始
		for j := 1; j <= n; j++ {
			if s[i-1] == t[j-1] { //如果当前两个字符相同, dp[i][j] = 两字符串同时向前一步数量 + 即使相同,也不取字符串1当前字符的情况
				dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
			} else { //如果不相同,那么肯定不能取字符串1中的当前字符
				dp[i][j] = dp[i-1][j]
			}
		}
	}

	return dp[m][n] //返回dp数组的最右下角值即可
}
